#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&&tqId=33257&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
"""


class Solution:
    def cutRope(self, rope_length):
        # 长度为1, 2, 3时, 答案比较恶心.(按理答案应该是1, 2, 3. 但是oj的答案是1, 1, 2. 所以只能if, else了)
        if rope_length == 1 or rope_length == 2:
            return 1

        if rope_length == 3:
            return 2

        capacity = max(rope_length, 3)

        dp = (capacity + 1) * [None]

        dp[1] = 1
        dp[2] = 2
        dp[3] = 3


        for acc_len in range(4, rope_length+1):
            max_multi = 0

            for part_len in range(1, acc_len//2 + 1):
                try_multi = dp[part_len] * dp[acc_len - part_len]
                if try_multi > max_multi:
                    max_multi = try_multi

            dp[acc_len] = max_multi

        return dp[rope_length]

def test():
    s = Solution()

    print(s.cutRope(1))
    print(s.cutRope(2))
    print(s.cutRope(3))
    print(s.cutRope(8))

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
